package array

import "sort"

// https://leetcode-cn.com/problems/3sum/
// 3数之和
// 算法: 双指针
// 先选定一个数字，作为基数，然后通过双指针找到两个满足3数和为0 的数字
// 时间复杂度: O(n^2)
func ThreeSum(nums []int) [][]int {
	sort.Ints(nums)
	retArr := make([][]int, 0)
	for index := 0; index < len(nums)-2; {
		start, end := index+1, len(nums)-1
		for start < end {
			currentSum := nums[start] + nums[end] + nums[index]
			var startMove, endMove bool
			switch {
			case currentSum == 0:
				// 存入正确的组合
				retArr = append(retArr, []int{nums[index], nums[start], nums[end]})
				startMove = true
				endMove = true
			case currentSum > 0:
				endMove = true
			case currentSum < 0:
				startMove = true
			}
			// 跳过所有重复的数字
			if startMove {
				for start < end && nums[start] == nums[start+1] {
					start++
				}
				start++
			}
			if endMove {
				for end > start && nums[end] == nums[end-1] {
					end--
				}
				end--
			}
		}
		// 跳过重复的数字
		nextIndex := index + 1
		for nextIndex < len(nums) && nums[nextIndex] == nums[index] {
			nextIndex++
		}
		index = nextIndex
	}
	return retArr
}
